// 求最长递增子序列的个数
// 贪心算法 + 二分查找

// 3 2 8 9 5 6 7 11 15 4

// 找到更具有潜力的
// 3
// 2
// 2 8
// 2 8 9
// 2 5 9
// 2 5 6
// 2 5 6 7 11 15

// 2 4 6 7 11 15

// 1.思路就是当前这一项比我们最后一项大则直接放在末尾
// 2.如果当前这一项比最够一项小，需要在序列中通过二分查找找到比当前大的一项，替换掉
// 3.最优的情况就是默认递增

function getSequence(arr) {
  const len = arr.length;

  const result = [0]; // 默认第0个为基准做序列
  const p = new Array(len).fill(0); // 标记索引
  let start;
  let end;
  let middle;
  let resultLastIndex;
  for (let i = 0; i < len; i++) {
    let arrI = arr[i];
    if (arrI !== 0) {
      // 忽略0 vue中序列0，表示没有意义需要创建
      resultLastIndex = result[result.length - 1];
      if (arr[resultLastIndex] < arrI) {
        // 比较最后一项和当前值，如果比最后一项大，则将当前索引放到结果集中
        result.push(i);
        p[i] = resultLastIndex; // 当前放在末尾要记住它前面的那个人是谁
        continue;
      }

      // 二分查找，在结果集中找到比当前值大的，用当前值的索引将其替换掉
      start = 0;
      end = result.length - 1;
      while (start < end) {
        // start === end的时候就停止
        middle = ((end + start) / 2) | 0;
        if (arr[result[middle]] < arrI) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }

      // 找到中间值后 需要替换
      if (arr[result[end]] > arrI) {
        result[end] = i;

        p[i] = result[end - 1]; // 记住他前面一个人是谁
      }
    }
  }
  // console.log(p);
  let i = result.length;
  let last = result[i - 1];

  while (i-- > 0) {
    // 倒叙追溯
    result[i] = last;
    last = p[last];
  }

  return result;
}

// console.log(getSequence([1, 2, 3, 4, 5, 6, 7, 0]));
// console.log(getSequence([3, 2, 8, 9, 5, 6, 7, 11, 15, 4]));
// console.log(getSequence([2,3,1,5,6,8,7,9,4]));
console.log(getSequence([5, 3, 4, 0]));
